from typing import List


class Solution:
    def sortArrayByParityII(self, A: List[int]) -> List[int]:
        # 需求:使得数组中任意一个数的索引的奇偶性与该数本身相同
        # 思路:先分成奇偶数两个数组,再拼接
        odd_list = []  # 奇数数组
        even_list = []  # 偶数数组
        for i in A:
            if i % 2 == 0:
                even_list.append(i)
            else:
                odd_list.append(i)
        # 排序数组
        odd_list.sort()
        even_list.sort()

        # 拼接数组
        result_list = []
        for i in range(len(odd_list)):
            result_list.append(even_list[i])
            result_list.append(odd_list[i])
        return result_list


# 输入：
l01 = [4, 2, 5, 7]
solution = Solution()
# 输出：[4, 5, 2, 7], [4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
print(solution.sortArrayByParityII(l01))
